package com.xinheyun.demo.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import javafx.util.Pair;
import lombok.Data;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/15 15:24
 * @version:v1.0
 */
public class test576 {

    public static void main(String[] args) {
        Solution5761 solution576 = new Solution5761();
        System.out.println(solution576.findPathsMy(2, 2, 2, 0, 0));
    }
}

@Data
class Solution576 {


    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        Deque<Pair<Integer, Integer>>[] queue = new Deque[maxMove + 1];
        int res = 0;
        queue[0] = new ArrayDeque<>();
        queue[0].add(new Pair<>(startRow, startColumn));
        for (int i = 0; i < maxMove; i++) {
            queue[i + 1] = new ArrayDeque<>();
            while (!queue[i].isEmpty()) {
                Pair<Integer, Integer> remove = queue[i].remove();
                int x = remove.getKey();
                int y = remove.getValue();
                if (x - 1 >= 0) {
                    queue[i + 1].add(new Pair<>(x - 1, y));
                } else {
                    res++;
                }
                if (x + 1 < m) {
                    queue[i + 1].add(new Pair<>(x + 1, y));
                } else {
                    res++;
                }
                if (y - 1 >= 0) {
                    queue[i + 1].add(new Pair<>(x, y - 1));
                } else {
                    res++;
                }
                if (y + 1 < n) {
                    queue[i + 1].add(new Pair<>(x, y + 1));
                } else {
                    res++;
                }
                if (res > 1000000007) {
                    res = res % 1000000007;
                }
            }


        }

        return res;
    }


}

class Solution5761 {

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][][] dp = new int[maxMove + 1][m][n];
        dp[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count = dp[i][j][k];
                    if (count > 0) {
                        for (int[] direction : directions) {
                            //j1,k1及坐标移动后的位置
                            int j1 = j + direction[0], k1 = k + direction[1];
                            if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
                            } else {
                                outCounts = (outCounts + count) % MOD;
                            }
                        }
                    }
                }
            }
        }
        return outCounts;
    }


    public int findPathsMy(int m, int n, int maxMove, int startRow, int startColumn) {
        int finalCounts = 0;
        final int MOD = 1000000007;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][][] paths = new int[maxMove+1][m][n];
        int count = 0;
        paths[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    count = paths[i][j][k];
                    if (count > 0) {
                        for (int[] d : directions) {
                            int j1 = j - d[0], k1 = k - d[1];
                            if (j1 >= 0 && j1 < n && k1 >= 0 && k1 < m) {
                                paths[i + 1][j1][k1] = (paths[i + 1][j1][k1] + count) % MOD;
                            } else {
                                finalCounts += count;
                                finalCounts %= MOD;
                            }

                        }

                    }
                }
            }
        }
        return finalCounts;
    }
}




